package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/3sum-closest/">16. 最接近的三数之和</a>
 */
class Solution16 {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var rst = Int.MAX_VALUE
        nums.sort()
        var i = 0
        while (i < nums.size - 2) {
            var l = i + 1
            var r = nums.size - 1
            while (l < r) {
                val sum = nums[l] + nums[r] + nums[i]
                rst = moreClose(target, rst, sum)
                if (sum > target) {
                    r--
                } else if (sum < target) {
                    l++
                } else {
                    return target
                }
            }
            while (i < nums.size - 2) {
                i++
                if (nums[i - 1] != nums[i]) {
                    break
                }
            }
        }
        return rst
    }

    fun moreClose(target: Int, a: Int, b: Int): Int {
        return if (Math.abs(a - target) > Math.abs(b - target)) b else a
    }
}

fun main() {
    println(Solution16().threeSumClosest(arrayOf(-1, 2, 1, -4).toIntArray(), 1))
}